package leetcode.hot100;

import java.util.Stack;

@SuppressWarnings("all")
public class _739_每日温度_单调栈 {

    // 请根据每日 气温 列表，重新生成一个列表
    // 对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替
    // 例如，给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) return null;
        // 使用单调栈解决，栈中存储的是温度对应的索引
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            // 当前温度
            int temperature = temperatures[i];
            // 在栈不为空的前提下，当前温度和栈顶温度比较，如果当前温度更高，那么就通过当前温度索引减去栈顶温度索引，即得到气温升高需等待天数
            // 需要保证栈顶元素最小，所以要继续用当前元素循坏比较
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int stackTopIndex = stack.pop();
                result[stackTopIndex] = i - stackTopIndex;
            }
            // 压入当前温度对应的索引，栈顶元素是栈中的最小值
            stack.push(i);
        }
        return result;
    }
}

// 维护一个存储下标的单调栈，从栈底--->栈顶的下标对应的温度列表中的温度依次递减(⬇️)，如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标
// 正向遍历温度列表：对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈
// 如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]
// 如果 当前温度 > 栈顶温度，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex
// 重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈